#pragma once

#include <d3dx9math.h>
#include <float.h>
#include <math.h>
#include <vector>

using namespace std;


#define CRT_MATH_EPSILON	(0.0000001f)
#define CRT_MATH_PI			(3.1415926535897f)

inline bool IsZero(float f)
{
	return fabs(f) < CRT_MATH_EPSILON;
}

inline bool fEqual(float a, float b)
{
	return IsZero(a - b);
}

inline int ClampInt(int src, int floor, int ceil)
{
	if (src < floor)
		return floor;
	else if (src > ceil)
		return ceil;
	else return src;
}

inline unsigned char ClampUChar(int source)
{
	unsigned char result = 0;

	if (source < 0)
		result = 0;
	else if (source > 255)
		result = 255;
	else
		result = (unsigned char)source;
	
	return result;
}

inline unsigned char ClampUChar(float source)
{
	unsigned char result = 0;

	if (source < 0)
		result = 0;
	else if (source > 255.0f)
		result = 255;
	else 
		result = (unsigned char)source;

	return result;
}

inline float ClampFloat(float src, float floor, float ceil)
{
	if (src < floor)
		return floor;
	else if (src > ceil)
		return ceil;
	else return src;
}

/*
/////////////////////////////////////////////////////////////////////
		vector3 lib
/////////////////////////////////////////////////////////////////////
*/
struct VEC3
{
	float x,y,z;

	VEC3() { x = y = z = 0; }
	VEC3(float f) { x = y = z = f; }
	VEC3(float _x, float _y, float _z) { x = _x; y = _y; z = _z; }
	VEC3(const VEC3& s) { x = s.x; y = s.y; z = s.z; } 
	VEC3(const D3DXVECTOR3& v) { x = v.x; y = v.y; z = v.z; }

	VEC3 operator+( const VEC3& t ) const
	{
		return VEC3(x + t.x, y + t.y, z + t.z); 
	}

	VEC3& operator+= (const VEC3& v)
	{
		x += v.x;
		y += v.y;
		z += v.z;
		
		return *this;
	}

	VEC3 operator-( const VEC3& t ) const
	{
		return VEC3(x - t.x, y - t.y, z - t.z); 
	}

	VEC3 operator*( float s ) const
	{
		return VEC3(x * s, y * s, z * s);
	}

	VEC3 operator*( const VEC3& v ) const
	{
		return VEC3(x * v.x, y * v.y, z * v.z);
	}

	VEC3& operator *= ( const VEC3& v )
	{
		*this = *this * v;
		return *this;
	}

	VEC3 operator -() const
	{
		return VEC3(-x, -y, -z);
	}

	const float* operator&() const { return &x; }
	float* operator&() { return &x; }

	float Size() const { return x * x + y * y + z * z; }
	float Length() const { return sqrtf(Size()); }
	
	// mirror current vector to the axis, all vectors are pre-normalized
	VEC3 Mirror(const VEC3& axis) const 
	{ 
		float proj = Dot(axis);

		VEC3 parallCom = axis * proj;
		VEC3 perpenCom = parallCom - *this;
		
		return perpenCom + parallCom;
	}		
	float Dot(const VEC3& v) const { return x * v.x + y * v.y + z * v.z; }
	float Dot_Saturate(const VEC3& v) const { return ClampFloat(Dot(v), 0.0f, 1.0f); }
	VEC3 CrossR(const VEC3& v)	// right handed
	{
		return VEC3(y * v.z - z * v.y, z * v.x - x * v.z, x * v.y - y * v.x);
	}
	VEC3 CrossL(const VEC3& v)	// left handed
	{
		return VEC3(-y * v.z + z * v.y, -z * v.x + x * v.z, -x * v.y + y * v.x);
	}

	// gamma correction
	VEC3 Gamma(float g)
	{
		return VEC3( powf(x, g), powf(y, g), powf(z, g) );
	}

	void Normalize() 
	{
		float l = Length();

		if (IsZero(l))
		{
			x = y = z = 0;
		}
		else
		{
			l = 1.0f / l;
			x *= l;
			y *= l;
			z *= l;
		}
	}

	//VEC3& operator= (const float* s)
	//{
	//	x = s[0];
	//	y = s[1];
	//	z = s[2];

	//	return *this;
	//}

	VEC3& operator= (const VEC3& s)
	{
		x = s.x;
		y = s.y;
		z = s.z;

		return *this;
	}
};



inline VEC3 Minimum(VEC3& a, VEC3& b)
{
	VEC3 result;
	result.x = min(a.x, b.x);
	result.y = min(a.y, b.y);
	result.z = min(a.z, b.z);

	return result;
}

inline VEC3 Maximum(VEC3& a, VEC3& b)
{
	VEC3 result;
	result.x = max(a.x, b.x);
	result.y = max(a.y, b.y);
	result.z = max(a.z, b.z);

	return result;
}

/*
/////////////////////////////////////////////////////////////////////
		vector2 lib
/////////////////////////////////////////////////////////////////////
*/

struct VEC2
{
	float x,y;

	VEC2() { x = y = 0; }
	VEC2(float f) { x = y = f; }
	VEC2(float _x, float _y) { x = _x; y = _y; }

	VEC2 operator+( const VEC2& t ) const
	{
		return VEC2(x + t.x, y + t.y); 
	}

	VEC2& operator+= (const VEC2& v)
	{
		x += v.x;
		y += v.y;

		return *this;
	}

	VEC2 operator-( const VEC2& t ) const
	{
		return VEC2(x - t.x, y - t.y); 
	}

	VEC2 operator*( float s ) const
	{
		return VEC2(x * s, y * s);
	}

	VEC2 operator*( const VEC2& v ) const
	{
		return VEC2(x * v.x, y * v.y);
	}

	VEC2& operator *= ( const VEC2& v )
	{
		*this = *this * v;
		return *this;
	}
};

/*
/////////////////////////////////////////////////////////////////////
		matrix44 lib (row majored)
/////////////////////////////////////////////////////////////////////
*/

struct MAT4
{
	float m[16];

	MAT4() { memset(m, 0, sizeof(float) * 16); }
	MAT4(const float* s) { memcpy(m, s, sizeof(float) * 16); }

	VEC3 TransformVector( VEC3& v )
	{
		VEC3 result;

		result.x = m[0] * v.x + m[1] * v.y + m[2] * v.z + 1;
		result.y = m[4] * v.x + m[5] * v.y + m[6] * v.z + 1;
		result.z = m[8] * v.x + m[9] * v.y + m[10] * v.z + 1;

		// ignore the w component

		return result;
	}
};

/*
/////////////////////////////////////////////////////////////////////
		color lib
/////////////////////////////////////////////////////////////////////
*/

struct COLOR
{
	unsigned char r,g,b,a;

	static const COLOR BLACK;
	static const COLOR WHITE;

	COLOR() { r = g = b = a = 0; }
	COLOR(unsigned char _r, unsigned char _g, unsigned char _b, unsigned char _a = 255) { r = _r; g = _g; b = _b; a = _a; }

	// if positive == true, the range of v should be [0, 1]
	// otherwise [-1, 1]
	COLOR(VEC3& v, bool positiveOnly) 
	{
		if (positiveOnly)
		{
			r = ClampUChar(255.0f * v.x);
			g = ClampUChar(255.0f * v.y);
			b = ClampUChar(255.0f * v.z);
		}
		else
		{
			r = ClampUChar(127.5f * v.x + 127.5f);
			g = ClampUChar(127.5f * v.y + 127.5f);
			b = ClampUChar(127.5f * v.z + 127.5f);
		}
	}
	void Randomize();

	VEC3 GetVec3() { return VEC3(r / 255.0f, g / 255.0f, b / 255.0f); }

	COLOR operator*( float s ) const
	{
		return COLOR((unsigned char)(r * s), (unsigned char)(g * s), (unsigned char)(b * s));
	}
};

/*
/////////////////////////////////////////////////////////////////////
		axis-aligned bounding box lib
/////////////////////////////////////////////////////////////////////
*/

struct AABB
{
	VEC3	minV;
	VEC3	maxV;

	AABB() { Init(); }
	AABB(VEC3& minv, VEC3& maxv) : minV(minv), maxV(maxv) {}
	void Init()	{ maxV = -FLT_MAX; minV = FLT_MAX; }
	AABB& operator +=(VEC3& v) { minV = Minimum(v, minV); maxV = Maximum(v, maxV); return *this; }
	AABB& operator +=(AABB& s) { minV = Minimum(s.minV, minV); maxV = Maximum(s.maxV, maxV); return *this; }

	void Intersect(AABB& other, AABB& result)
	{
		result.minV = Maximum(minV, other.minV);
		result.maxV = Minimum(maxV, other.maxV);
	}

	VEC3 GetCenter() const { return (minV + maxV) * 0.5f; }
	VEC3 GetSize() const { return (maxV - minV) * 0.5f; }

	AABB OctSplit(int index)	// index - [0, 7]
	{
		AABB result;

		result.minV = minV;

		VEC3 size = (maxV - minV) * 0.5f;

		if (index & 1)
			result.minV.x += size.x;

		if (index & 2)
			result.minV.y += size.y;

		if (index & 4)
			result.minV.z += size.z;

		result.maxV = result.minV + size;

		return result;
	}

	VEC3 Vertex(int i) { return VEC3((i&1 ? minV.x : maxV.x), (i&2 ? minV.y : maxV.y), (i&4 ? minV.z : maxV.z)); }

	bool ContainPoint(const VEC3& p) const
	{
		return p.x >= minV.x
			&& p.y >= minV.y
			&& p.z >= minV.z
			&& p.x <= maxV.x
			&& p.y <= maxV.y
			&& p.z <= maxV.z;
	}

	bool Contain(const AABB& aAABB) const
	{
		return ContainPoint(aAABB.minV) && ContainPoint(aAABB.maxV);
	}
};

struct Frustum
{
	Frustum(VEC3& eyePos, VEC3& viewDir, VEC3& viewUp, float nearClip, float farClip, float fovX, float fovY);
	// Given camera position, view direction, up direction and an array of AABB, calculate the tight bounding frustum.
	Frustum(VEC3& eyePos, VEC3& viewDir, VEC3 &viewUp, vector<AABB>& aabb);
	// Given camera position, view direction, up direction and one frustum, calculate the tight bounding frustum.
	Frustum(VEC3& eyePos, VEC3& viewDir, VEC3 &viewUp, Frustum& f);
	// Given camera position, view direction, up direction and an array of vertices, calculate the tight bounding frustum.
	Frustum(VEC3& eyePos, VEC3& viewDir, VEC3 &viewUp, vector<VEC3>& vertices);
	Frustum(VEC3& eyePos, VEC3& viewDir, VEC3 &viewUp, VEC3 vertices[], int nVertex);

	VEC3 eye;
	VEC3 view;
	VEC3 up;
	float nearclip, farclip;
	float fovx, fovy;
	float aspect;

	VEC3 vert[8];	// could be derived from above parameters
	static int triangle_list[12 * 3];	// triangle index
	static int line_list[12 * 2];		// triangle index

	void UpdateVertex();	// Update the vert member
};

// Plane equation in 3D
struct FPlane
{
	VEC3	Normal;
	float	Distance;

	FPlane() {}
	FPlane(VEC3& n, float d): Normal(n), Distance(d) {}
	FPlane(VEC3 n, float d): Normal(n), Distance(d) {}

	bool AtFront(const VEC3& P) const { return P.Dot(Normal) + Distance >= 0.0f; }
	bool Intersect(VEC3& P0, VEC3& P1, VEC3& Output);
	bool Intersect(const struct RAY& Ray, VEC3& IP, float& IPDistance);
};


#define CONVEX_MAX_VERTEX	(16)
#define CONVEX_MAX_PLANE	(18)

// A plane to compose the convex hull, with N vertices
struct FConvexPlane
{
	VEC3			Vertices[CONVEX_MAX_VERTEX];
	int				nVertex;
	FPlane			Plane;	

	void SplitByPlane(FConvexPlane& FrontCP, FConvexPlane& BackCP, VEC3& P0, VEC3& P1, FPlane& SplitPlane);
	bool IsEmpty() { return nVertex == 0; }
	void AddVertex(VEC3& P);	// Add a vertex into the CP, if it's not existing now. Don't care about the order
	void SortVertices();		// Sort the vertices so that they're ordered counter-clockwisely
	void Flip();				// Flip the plane normal, and reverse the vertices order
	void Init(FPlane& P) { Plane = P; nVertex = 0; }


	FConvexPlane() { nVertex = 0; }
	//FConvexPlane(VEC3& P0, VEC3& P1, VEC3& P2, VEC3& P3);	// construct CP from 4 co-plane vertices
	FConvexPlane(VEC3 P0, VEC3 P1, VEC3 P2, VEC3 P3);	// construct CP from 4 co-plane vertices
};

struct FConvexHull
{
	FConvexPlane	Planes[CONVEX_MAX_PLANE];
	int				nPlane;

	FConvexHull() { nPlane = 0; }
	FConvexHull(Frustum& F, bool NeedUpperPlane);
	FConvexHull(AABB& B);

	void SplitByPlane(FConvexHull& FrontHull, FConvexHull& BackHull, FPlane& SplitPlane);
	void IntersectByConvexHull(FConvexHull& Result, FConvexHull& InConvex);
	bool IsEmpty() { return nPlane == 0; }
	void Clear() { nPlane = 0; }

	void AppendConvexPlane(FConvexPlane& Plane) { Planes[nPlane++] = Plane; }
	
	// Caller should reserve a buffer of minimum size (CONVEX_MAX_PLANE * CONVEX_MAX_VERTEX)
	int OutputVertex(VEC3 Output[], bool AllowRedundant);
};


/*
/////////////////////////////////////////////////////////////////////
		ray lib (defined by a starting point and direction)
/////////////////////////////////////////////////////////////////////
*/
struct RAY
{
	VEC3	origin;
	VEC3	direction;	// should be normalized already
	bool	inObj;		// this ray is inside object (normal should be reverted in this circumstance)

	// for ray/AABB intersection. 
	// http://tog.acm.org/resources/RTNews/html/rtnv19n1.html#art7
	VEC3	invDirection;
	int		sign[3];

	// These might be changed during a ray/scene intersection test
	VEC3	effectiveOrigin;
	VEC3	effectiveTarget;

	//VEC3	target;		// This value is calculated from origin/direction and size of the scene
	//VEC3	delta;		// delta = target - origin
	//RAY() {}
	//RAY(VEC3 o, VEC3 d, bool i) : origin(o), direction(d), inObj(i) {}	
};

bool RayIntersectTriangle( const RAY& ray, struct TCRTTriangleHelper& TriangleHelper, float &u, float &v, float &dist );

//bool RayIntersectAABB(RAY& ray, AABB& aabb, float& Distance, struct TOctree* pTree);

// The tree is uniformed split into size*size*size leaves. (size = 1 << (treeDepth-1))
// Each leaf has an associated index, the index is z - y - x majoyed.
// Check which leaves will be hit by the ray (ordered by hit sequence)
//bool RayIntersectTree(RAY& ray, AABB& rootAABB, int treeDepth, vector<int>& hitLeafArray, struct TOctree* pTree);

void TransformBoundingBox(D3DXMATRIXA16& View, D3DXVECTOR3& MinV, D3DXVECTOR3& MaxV, D3DXVECTOR3& NewMinV, D3DXVECTOR3& NewMaxV);